#include <iostream>

using namespace std;

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}
// 普通查找
char* strstr(const char* str, char* data)
{
	int index;
	int len;

	if(NULL == str || NULL == data)
		return NULL;

	len = strlen(data);
	while(*str && (int)strlen(str) >= len){
		for(index = 0; index < len; index++){
			if(str[index] != data[index])
				break;
		}
		if(index == len)
			return (char*) str;
		if('\0' == str[len])
			break;
		str ++;
	}

	return NULL;
}

// KMP 算法
//m  搜索开始    i   目标字符串开始处 
char* strstr(const char* str, char* data)
{
	int m=0, i=0;
	int len;
	int slen;
	char* T;

	if(NULL == str || NULL == data)
		return NULL;
	len = strlen(data);
	slen = strlen(str);
	T = produce_T(data, len);
	while(m+i < slen){
		if(data[i] == str[m+i]){
			if(i == len)
				return m;
			i++;
		}else{
			m = m + i - T[i];
			if(T[i] > -1)
				i = T[i];
			else
				i = 0;
		}
	}
}

char* produce_T(char* data, int len)
{
	char* T;
	T = (char*)malloc(sizeof(char)* len);
	T[0] = -1;
	T[1] = 0;
	int pos = 2, cnd = 0;

	while(pos < len)
	{
		if(data[pos-1] = data[cnd])
		{
			cnd = cnd + 1;
			T[pos] = cnd;
			pos = pos + 1;
		}else if(cnd > 0)
		{
			cnd = T[cnd];
		}else
		{
			T[pos] = 0;
			pos++;
		}
	}
}